Search results for "Yen's algorithm"

showing 2 items of 2 documents

Implementation of algorithms forK shortest loopless paths

1986

Implementations of loopless k shortest path algorithms are examined. Efficient storage structures for a large number of paths are given. A fast algorithm for determining the shortest paths in Yen's method is developed. Timing experiments show that a hybrid of Clarke's and Yen's methods is generally the fastest, although not significantly. Using upper bounds for the lengths of paths essentially improves all methods.

Computer Networks and CommunicationsHardware and ArchitectureShortest path problemK shortest path routingFloyd–Warshall algorithmAlgorithmFast algorithmYen's algorithmSoftwareInformation SystemsMathematicsNetworks
researchProduct

A class of label-correcting methods for the K shortest paths problem

2001

In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that: 1. some label-correct…

Discrete mathematicsManagement Science and Operations ResearchComputer Science ApplicationsEuclidean shortest pathShortest Path Faster AlgorithmSettore SECS-S/06 -Metodi Mat. dell'Economia e d. Scienze Attuariali e Finanz.Shortest path problemK shortest path routingCanadian traveller problemYen's algorithmConstrained Shortest Path FirstDistanceK shortest paths problem label correcting methodsMathematics
researchProduct